<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 1. 统计和小于目标的下标对数目
        // 时间复杂度：O(n^3)
        // 空间复杂度：O(1)
        var fourSum = function(nums, target) {
            // 排序
            nums.sort((a, b) => a - b)
            let ans = []
            let n = nums.length
            for (let a = 0; a < nums.length - 3; a++) {
                let x = nums[a]
                // 优化一：如果出现重复的a，则直接continue
                if (a > 0 && x === nums[a - 1]) {
                    continue
                }
                // 优化二：如果当前四个数已经比target大，后续的肯定都更大，则没有满足条件的
                let s = x + nums[a + 1] + nums[a + 2] + nums[a + 3]
                if (s > target) {
                    break
                }
                // 优化三：如果当前四个数,这里容易出错，枚举的只有a，所以是x和最后三个数
                s = x + nums[n - 3] + nums[n - 2] + nums[n - 1]
                if (s < target) {
                    continue
                }
                
                for (let b = a + 1; b < nums.length - 2; b++) {
                    let y = nums[b]
                    // 优化一：如果出现重复的a，则直接continue
                    if (b > a + 1 && y === nums[b - 1]) {
                        continue
                    }
                    // 优化二：容易写错，是b+1和b+2
                    s = x + y + nums[b + 1] + nums[b + 2]
                    if (s > target) {
                        break
                    }
                    // 优化三：容易写错，是x+y和最后的n-1和n-2的数
                    s = x + y + nums[n - 1] + nums[n - 2]
                    if (s < target) {
                        continue
                    }

                    let c = b + 1
                    let d = n - 1
                    while (c < d) {
                        s = x + y + nums[c] + nums[d]
                        if (s < target) {
                            c++
                        } else if (s > target) {
                            d--
                        } else {
                            ans.push([x, y, nums[c], nums[d]])
                            // 这个写法是为了跳过重复的c和d，防止在结果数组中添加重复的元素
                            for (c++; c < d && nums[c] === nums[c - 1]; c++) {
                                continue
                            }
                            for (d--; c < d && nums[d] === nums[d + 1]; d--) {
                                continue
                            }
                        }
                    }
                }
            }
            return ans
        };
        console.log(fourSum([-1,0,1,2,-1,-4], -1));
        // console.log(fourSum([1, 0, -1, 0, -2, 2], 0));
        // console.log(threeSumClosest([-1,2,1,-4], 1));
    </script>
</body>
</html>